package graph;

import java.util.Arrays;

/**
 * O(v*e^2) Max flow EdmondsKarp solution
 * 
 * @author yinzichen
 * 
 */
class EdmondsKarp {

	public int edmondsKarp(int[][] graph, int vertexNum, int src, int dest) {
		int[][] remain = new int[vertexNum][vertexNum];
		for (int i = 0; i < vertexNum; i++) {
			for (int j = 0; j < vertexNum; j++) {
				remain[i][j] = graph[i][j];
			}
		}
		int totFlow = 0;
		int[] q = new int[vertexNum];
		int[] flow = new int[vertexNum];
		int[] prev = new int[vertexNum];
		while (true) {
			int head = 0, rear = -1;
			Arrays.fill(flow, 0);
			q[++rear] = src;
			flow[src] = Integer.MAX_VALUE;
			boolean find = false;
			while (head <= rear && !find) {
				int u = q[head++];
				for (int v = 0; v < vertexNum; v++) {
					if (flow[v] == 0 && remain[u][v] > 0) {
						flow[v] = Math.min(flow[u], remain[u][v]);
						prev[v] = u;
						if (v == dest) {
							find = true;
							break;
						}
						q[++rear] = v;
					}
				}
			}
			if (!find)
				break;
			for (int i = dest; i != src; i = prev[i]) {
				remain[prev[i]][i] -= flow[dest];
				remain[i][prev[i]] += flow[dest];
			}
			totFlow += flow[dest];
		}
		return totFlow;
	}
}
